This invention relates to a method and apparatus for the lossless compression of data.
While lossy data compression hardware has been available for image and signal processing for some years, lossless data compression has only recently become of interest, as a result of increased commercial pressure on bandwidth and cost per bit in data storage and data transmission; also, reduction in power consumption by reducing data volume is now of importance.
The principle of searching a dictionary and encoding data by reference to a dictionary address is well known, and the apparatus to apply the principle consists of a dictionary and a coder/decoder.
In Proceedings of EUROMICRO-22, 1996, IEEE, xe2x80x9cDesign and Performance of a Main Memory Hardware Data Compressorxe2x80x9d, Kjelso, Gooch and Jones describe a novel compression method, termed the X-Match algorithm, which is efficient at compressing small blocks of data and suitable for high speed hardware implementation.
The X-Match algorithm maintains a dictionary of data previously seen, and attempts to match a current data element, referred to as a tuple, with an entry in the dictionary, replacing a matched tuple with a shorter code referencing the match location. The algorithm operates on partial matching, such as 2 bytes in a 4 byte data element. In Proceedings of EUROMICRO-25, 1999, IEEE, xe2x80x9cThe X-MatchLITE FPGA-Based Data Compressorxe2x80x9d, Nunez, Feregrino, Bateman and Jones describe the X-Match algorithm implemented in a Field Programmable Gate Array (FPGA) prototype.
It is an object of the invention to provide a lossless data compression algorithm which can compress data more effectively than is possible with the published arrangement.
According to the invention, a lossless data compression system comprising a content addressable memory dictionary and a coder, characterised by run length encoding means connected to receive the output of the coder, said encoding means being arranged to count the number of times a match consecutively occurs at a predetermined dictionary location.
Also according to the invention, a lossless method of compressing data comprising the steps of:
comparing a search tuple of fixed length with a plurality of tuples of said fixed length stored in a dictionary;
indicating the location in the dictionary of a full or partial match or matches;
selecting a best match of any plurality of matches; and
encoding the match location and the match type;
characterised by the further steps of:
loading each search tuple in turn into the same address in the dictionary;
and counting the number of times identical tuples are matched consecutively into said address.
Preferably said same address as the first location in the dictionary.
In the drawings, FIG. 1 illustrates the architecture of a compressor arrangement published by Nunez et al.